package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * @author qidi
 * @date 2022-01-06 11:31:54
 */
class Q0108_ConvertSortedArrayToBinarySearchTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums.length == 1) return new TreeNode(nums[0]);

            return process(nums, 0, nums.length - 1);
        }

        private TreeNode process(int[] nums, int l, int r) {
            if (l > r) return null;

            int rooti = (r + l) / 2;
            TreeNode root = new TreeNode(nums[rooti]);

            root.left = process(nums, l, rooti - 1);
            root.right = process(nums, rooti + 1, r);

            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0108_ConvertSortedArrayToBinarySearchTree().new Solution();
        solution.sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
        solution.sortedArrayToBST(new int[]{1, 3});
    }
}